package haxe.util;

import haxe.util.LinkedList;
import haxe.util.Compare;
import haxe.util.SortedCollection;
import haxe.util.Stack;

typedef HEntry = {
	var next:HEntry;
	var prev:HEntry;
	var value:Dynamic;
	var left:HEntry;
	var right:HEntry;
	var parent:HEntry;
}


class LinkedHeap<T> extends SortedCollection<T>
{
	public var size(getSize,null):Int;
	
	private var _s:Int;
	private var _f:HEntry;//root
	private var _l:HEntry;//last node
	
	public function new( c:Comparator<T> )
	{
		super(c);
		_s = 0;
	}
	
	public function add( o:T ):Void
	{
		super.add(o);
		addLast(o);
		var e:HEntry = _l;
		var t:T;
		//comp( _a[i], _a[j] ) < 0
		while( e != _f && comp( e.value, e.parent.value ) < 0 )
		{
			t = e.value;e.value = e.parent.value;e.parent.value = t;//swap
			e = e.parent;
		}
	}
	
	public function extract( ):T
	{
		var r:T = _f.value;
		_f.value = removeLast();
		if ( _s > 2 )
		{
			//restoring Heap property
			var e:HEntry = _f;
			var f:HEntry = if ( comp( e.left.value, e.right.value ) < 0 )e.left; else e.right;//minimal child
			var t:T;
			while ( comp( e.value, f.value ) > 0 )
			{
				t = e.value;e.value = f.value;f.value = t;//swap
				e = f;
				if (e.left == null )
					break;
				f = 
				#if neko
				if( e.right != null )
				{
					if ( comp( e.left.value, e.right.value ) < 0 ) e.left; else e.right;
				}else
					e.left;
				#else true
				if ( comp( e.left.value, e.right.value ) < 0 ) e.left; else e.right;//get minimal child
				#end
			}
		}
		else if ( _s == 2 && comp( _f.value, _l.value ) > 0 )
		{
			var t:T;
			t = _f.value;_f.value = _l.value;_f.value = t;//swap
		}
		return r;
	}
	
	public function getFirst():T
	{
		return _f.value;
	}
	
	public function insert( o:T ):Void
	{
		add(o);
	}
	
	//todo - OPT !
	public function remove(o:T, ?equals: T->T->Bool):Bool
	{
		if ( equals == null ) equals = eq;
		if ( comp( o, _f.value ) >= 0 && contains(o) )
		{
			var s:Stack<T> = new Stack();
			var i:T = extract();
			while(! equals( i, o ) )
			{
				s.push(i);
				i = extract();
			}
			while( !s.isEmpty() )
			{
				add( s.pop() );
			}
			return true;
		}else
			return false;
	}
	
	public function contains(o:T, ?equals: T->T->Bool ):Bool
	{
		if ( comp(o, _f.value ) >= 0 )
		{
			for ( i in this )
			{
				if ( comp( o, i ) == 0 )
					return true;
			}
			return false;
		}else
			return false;
	}
	
	public function clear():Void
	{
		_s = 0;
		_f = _l = null;
	}
	
	public function isEmpty():Bool
	{
		return _s == 0;
	}
	
	//WARNNING - not SORTED
	public function iterator():Iterator<T>
	{
		return new ListIterator(cast _f);
	}
	
	public function toString():String
	{
		return "LinkedHeap";
	}
	
	private function getSize():Int
	{
		return _s;
	}
	
	private function addLast(o:T):Void
	{
		if ( _s > 1)
		{
			if( _l == _l.parent.right ) 
			{
				_l.next = {next:null, prev:_l, value:o, parent:_l.parent.next, left:null,right:null};
				_l.parent.next.left = _l.next;
			}
			else
			{
				_l.next = {next:null, prev:_l, value:o, parent:_l.parent, left:null,right:null};
				_l.parent.right = _l.next;
			}
			_l = _l.next;
			
		}
		else if ( _s == 1 )
		{
			_l.next = {next:null, prev:_l, value:o, parent:_f, left:null,right:null};
			_f.left = _l.next;
			_l = _l.next;
		}
		else 
		{
			_f = _l = { parent:null,left:null,right:null,value:o, next:null, prev:null};
		}
		++_s;
	}
	
	//todo - test neko
	private function removeLast():T
	{		
		if ( _s > 0 )
		{
			var r:T = _l.value;
			if ( _s == 1 )
			{
				_f = _l = null;
			}else{
				var r:T = _l.value;
				if ( _l.parent.left == _l )
					_l.parent.left = null;
				else
					_l.parent.right = null;
				_l = _l.prev;
				_l.next = null;
			}
			--_s;
			return r;
		}else
			return null;
	}
	
	
	public static function main():Void
	{
		//Logger.setRedirection();
		var N:Int = 10000;
		var ah:ArrayHeap<Int> = new ArrayHeap(null);
		var lh:LinkedHeap<Int> = new LinkedHeap(null);
		var m:LinkedList<Int> = new LinkedList();
		var a:Array<Int> = new Array();
		var v:Array<Int> = new Array();
		var k:List<Int> = new List();
		
		var getTime:Dynamic = 
		#if flash
			flash.Lib.getTimer;
		#else neko
			neko.Sys.time;
		#else js
			null;
		#end
		
		
		for( i in 0...N )
			v.push( Math.round( Math.random()*N ) );
		
		var t:Int = getTime();
		for ( i in v )
			a.push(i);
		trace("Array pushing time : "+( getTime()-t));
					
		t = getTime();
		for ( i in v )
			ah.add(i);
		trace("ArrayHeap adding time : "+( getTime()-t));
		
		t = getTime();
		for ( i in v )
		{
			lh.add(i);
		}
		trace("LinkedHeap adding time : "+( getTime()-t));
		
		t = getTime();
		for ( i in v )
		{
			m.add(i);
		}
		trace("LinkedList adding time : "+( getTime()-t));
		
		t = getTime();
		for ( i in v )
			k.add(i);
		trace("List adding time : "+(getTime()-t));
		
		////////////////////////////////////////
		//	Extracting
		///////////////////////////////////////
		
		t = getTime();
		while( !ah.isEmpty() )
			ah.extract();
		trace("ArrayHeap extracting time : "+(getTime()-t));
		
		t = getTime();
		while( !lh.isEmpty() )
			lh.extract();
		trace("LinkedHeap extracting time : "+(getTime()-t));
		
		t = getTime();
		while( !m.isEmpty() )
			m.removeFirst();
		trace("LinkedList removing time : "+(getTime()-t));
		
		t = getTime();
		while( a.length != 0 )
			a.shift();
		trace("Array shifting time : "+(getTime()-t));
		
		t = getTime();
		while( ! k.isEmpty() )
			k.pop();
		trace("List poping time : "+(getTime()-t));
		
		////////////////////////////////////////
		//	Check sorting
		///////////////////////////////////////
		
		for ( i in v )
		{
			ah.add(i);
			lh.add(i);
			a.push(i);
		}
		
		var c:Comparator<Int> = IntComparator.getInstance();
		t = getTime();
		a.sort(c.compare);
		trace("Array first sorting time : "+(getTime()-t));
		
		a.push(Math.round( Math.random()*100) );
		
		t = getTime();
		a.sort(c.compare);
		trace("Array second sorting time : "+(getTime()-t));
		
		var i:Int = 0;
		var hv:Int;
		var lv:Int;
		var q:Queue<Int> = new Queue();
		var k:Queue<Int> = new Queue();
		while( !ah.isEmpty())
		{
			q.enqueue(ah.extract());
			k.enqueue(lh.extract());
		}
		trace(">"+q.toArray().join("|").substr(0,60));
		trace(">"+k.toArray().join("|").substr(0,60));
		trace(">"+a.join("|").substr(0,60));
		trace("ArrayHeap|LinkedHeap|Array");
	}
}